package 题目集.动态规划.最长公共子串;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
 */
public class 环绕字符串中唯一的子字符串 {

    /**
     * 记录下每个位置的最长连续长度，然后统计每个字符的最长连续长度
     */
    public int findSubstringInWraproundString(String s) {
        int[] dp=new int[s.length()];
        Arrays.fill(dp,1);
        char next=s.charAt(dp.length-1);
        for (int i = dp.length - 2; i >= 0; i--) {
            char cur=s.charAt(i);
            if (check(cur,next)){
                dp[i]+=dp[i+1];
            }
            next=cur;
        }
        int[] count=new int[26];
        for (int i = 0; i < dp.length; i++) {
            int index = s.charAt(i) - 'a';
            count[index] =Math.max(count[index],dp[i]);
        }
        int sum=0;
        for (int i = 0; i < count.length; i++) {
            sum+=count[i];
        }
        return sum;
    }
    public boolean check(char cur,char next){
        if (cur=='z'){
            return next=='a';
        }
        return cur+1==next;
    }
    @Test
    public void test(){
        String str="zab";
        int res = findSubstringInWraproundString(str);
        System.out.println(res);
    }
}
